// https://www.lintcode.com/problem/sort-integers-ii/my-submissions

class Solution {
public:
    /**
     * @param A: an integer array
     * @return: nothing
     */
    // quick sort
    // void quickSort(vector<int> &nums, int low, int high)
    // {
    //     int start = low;
    //     int end = high;
    //     int mid = (end - start) / 2 + start;
    //     int pivot = nums[mid];
    //     while (start < end)
    //     {
    //         while (nums[start] < pivot) start++;
    //         while (nums[end] > pivot) end--;
    //         if (start <= end)
    //         {
    //             swap(nums[start], nums[end]);
    //             start++;
    //             end--;
    //         }
    //     }
    //     if (end > low) quickSort(nums, low, end);
    //     if (start < high) quickSort(nums, start, high);
    // }
    // void sortIntegers2(vector<int> &A) {
    //     if (A.empty()) return;
    //     quickSort(A, 0, A.size() - 1);
    // }


    void quickSort(vector<int> &nums, int low, int high)
    {
        if (low >= high) return; //加了这句，最后两行就不用判断了
        int start = low;
        int end = high;
        int mid = (end - start) / 2 + start;
        int pivot = nums[mid];
        while (start < end) //这一句必须要，要把所有能交换的都交换掉
        {
            while (nums[start] < pivot) start++;
            while (nums[end] > pivot) end--;
            if (start <= end)
            {
                swap(nums[start], nums[end]);
                start++;
                end--;
            }
        }
        quickSort(nums, low, end);
        quickSort(nums, start, high);
    }
    void sortIntegers2(vector<int> &A) {
        if (A.empty()) return;
        quickSort(A, 0, A.size() - 1);
    }


    // heap sort 超时？
    // void heapify(vector<int> &A, int num)
    // {
    //     int l = num * 2 + 1;
    //     int r = num * 2 + 2;
    //     int min = num;
    //     // if (A[l] > A[num]) max = l;
    //     // if (A[r] > A[num]) max = r; 注意边界判断；注意是找三者中最大的，
    //     // 是和A[max]比较
    //     if (l < A.size() && A[l] < A[min]) min = l;
    //     if (r < A.size() && A[r] < A[min]) min = r;
    //     if (min == num) return;
    //     swap(A[num], A[min]);
    //     heapify(A, min);
    // }
    // void minHeapify(vector<int> &A) {
    //     // for (int i = size / 2 - 1; i >= 0; i--) 不要瞎写，父节点
    //     for (int i = A.size() / 2; i >= 0; i--)
    //     {
    //         heapify(A, i);
    //     }
    // }
    // void sortIntegers2(vector<int> &A) {
    //     minHeapify(A);
    //     vector<int> result;
    //     for (int i = A.size() - 1; i >= 0; --i)
    //     {
    //         result.push_back(A[0]);
    //         swap(A[0], A[i]);
    //         A.pop_back();
    //         minHeapify(A);       
    //         //注意不从A里面去除的话 最后一个还是会被比较到。  
    //     }
    //     A = result;
    // }
    
    // merge sort 漏洞百出的一版
    // void mergeSort(vector<int> &A, int start, int end)
    // {
    //     if (start >= end) return; // 用到递归一定别忘了停止条件！
    //     int mid = (end - start) / 2 + start;
    //     mergeSort(A, 0, mid);
    //     mergeSort(A, mid + 1, end);
    //     vector<int> tmp;
    //     int l = 0;
    //     int r = mid + 1;
    //     while (l <= mid && r <= end)
    //     {
    //         if (A[l] < A[r]) tmp.push_back(A[l++]);
    //         else tmp.push_back(A[r++]);
    //     }
    //     while (l <= mid) tmp.push_back(A[l++]);
    //     while (r <= end) tmp.push_back(A[r++]);
    //     A = tmp;
    // }
    // void sortIntegers2(vector<int> &A) {
    //     mergeSort(A, 0, A.size() - 1);
    // }

};


class Solution {
public:
    void mergeSort(vector<int>& nums, int start, int end, vector<int>& tmp) {
        if (start >= end) return;
        int mid = (end - start) / 2 + start;
        mergeSort(nums, start, mid, tmp);
        mergeSort(nums, mid + 1, end, tmp);
        int l = start, k = start, r = mid + 1;
        // vector<int> tmp(nums.size()); tmp传引用或者定义为全局数组节省时间
        while (l <= mid && r <= end) {
            if (nums[l] < nums[r])
                tmp[k++] = nums[l++];
            else
                tmp[k++] = nums[r++];
        }
        while (l <= mid) {
            tmp[k++] = nums[l++];
        }
        while (r <= end) {
            tmp[k++] = nums[r++];
        }
        // for (int i = 0; i < nums.size(); ++i) { 注意！！！
        for (int i = start; i <= end; ++i) {
            nums[i] = tmp[i];
        }
    }
    vector<int> sortArray(vector<int>& nums) {
        vector<int> tmp(nums.size());
        mergeSort(nums, 0, nums.size() - 1, tmp);
        return nums;
    }
};